package com.linzm.leetcode.primary.exercises4_20230129;

import java.util.*;

/**
 * @Author zimingl
 * @Date 2023/2/5 17:38
 * @Description: 移除字母异位词后的结果数组
 * 输入：words = ["abba","baba","bbaa","cd","cd"]
 * 输出：["abba","cd"]
 * 解释：
 * 获取结果数组的方法之一是执行下述步骤：
 * - 由于 words[2] = "bbaa" 和 words[1] = "baba" 是字母异位词，选择下标 2 并删除 words[2] 。
 * 现在 words = ["abba","baba","cd","cd"] 。
 * - 由于 words[1] = "baba" 和 words[0] = "abba" 是字母异位词，选择下标 1 并删除 words[1] 。
 * 现在 words = ["abba","cd","cd"] 。
 * - 由于 words[2] = "cd" 和 words[1] = "cd" 是字母异位词，选择下标 2 并删除 words[2] 。
 * 现在 words = ["abba","cd"] 。
 * 无法再执行任何操作，所以 ["abba","cd"] 是最终答案。
 */
public class Demo13_2273 {
    public static void main(String[] args) {
        Demo13_2273 demo13_2273 = new Demo13_2273();
        String[] words = {"abba", "baba", "bbaa", "cd", "cd", "a", "a", "b", "a"};
        List<String> list = demo13_2273.removeAnagrams2(words);
        System.out.println(String.join(" ", list));
    }

    private List<String> removeAnagrams(String[] words) {
        List<String> list = new ArrayList<>();
        int left = 0;
        for (int i = 0; i < words.length; i++) {
            char[] chars1 = words[left].toCharArray();
            char[] chars2 = words[i].toCharArray();
            Arrays.sort(chars1);
            Arrays.sort(chars2);
            boolean equals = new String(chars1).equals(new String(chars2));
            if (!equals) {
                list.add(words[left]);
                left = i;
            }
            if (!equals && (i == words.length - 1)) {
                list.add(words[i]);
            }
            if (equals && (i == words.length - 1)) {
                list.add(words[left]);
            }
        }
        return list;
    }

    private List<String> removeAnagrams2(String[] words) {
        List<String> list = new ArrayList<>();
        Deque<String> stack = new LinkedList<>();
        for (int i = 0; i < words.length; i++) {
            char[] chars = words[i].toCharArray();
            Arrays.sort(chars);
            if (stack.isEmpty()) {
                stack.push(new String(chars));
                list.add(words[i]);
            }
            if (!stack.peek().equals(new String(chars))) {
                stack.push(new String(chars));
                list.add(words[i]);
            }
        }
        return list;
    }

    private boolean isSame(int[] arr1, int[] arr2) {
        if (arr1 == null || arr2 == null) {
            return false;
        }
        for (int i = 0; i < arr1.length; i++) {
            if (arr1[i] != arr2[i]) {
                return false;
            }
        }
        return true;
    }
}
